package com.leetcode.www;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-04-10
 * Time:22:21
 */
public class DP139 {
    public boolean wordBreak1(String s, List<String> wordDict) {
        Set<Integer> set = new HashSet<>();
        return dfs(s, wordDict, set, 0);
    }
    public boolean dfs(String s, List<String> wordDict, Set<Integer> set, int start) {
        if (start == s.length()) {//存在
            return true;
        }

        for (int i = start; i < s.length(); i++) {
            if (set.contains(i)) {//set里面已经有这个下标字符了
                continue;
            }
            if (wordDict.contains(s.substring(start, i + 1))) {//看字典里面是否存在部分字符串,如果存在就看目标单词后面的字符串是不是也在字典中
                if (dfs(s, wordDict, set, i + 1)) {
                    return true;
                }
                set.add(i);//证明这个字符前面的是可以在字典中找到的
            }
        }
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);//将字典放在set里面方便查找
        //状态定义F(i)表示前i个字符在字典里面能否找到
        //状态转移方程前i个字符存在,,加上第i个字符之后也满足
        //刚开始没有字符的时候应为true
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
